A re-order buffer (ROB) is a hardware unit used in an extension to the
Tomasulo algorithm
Tomasulo's algorithm is a computer architecture hardware algorithm for dynamic scheduling of instructions that allows out-of-order execution and enables more efficient use of multiple execution units. It was developed by Robert Tomasulo at IBM in ...
to support
out-of-order and
speculative
Speculative may refer to:
In arts and entertainment
*Speculative art (disambiguation)
*Speculative fiction, which includes elements created out of human imagination, such as the science fiction and fantasy genres
**Speculative Fiction Group, a Per ...
instruction execution. The extension forces instructions to be committed in-order.
The buffer is a
circular buffer
In computer science, a circular buffer, circular queue, cyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams. Ther ...
(to provide a
FIFO instruction ordering queue) implemented as an
array/vector (which allows recording of results against instructions as they complete out of order).
There are three stages to the Tomasulo algorithm: "Issue", "Execute", "Write Result". In an extension to the algorithm, there is an additional "Commit" stage. During the Commit stage, instruction results are stored in a register or memory. The "Write Result" stage is modified to place results in the re-order buffer. Each instruction is tagged in the
reservation station
A unified reservation station, also known as unified scheduler, is a decentralized feature of the microarchitecture of a CPU that allows for register renaming, and is used by the Tomasulo algorithm for dynamic instruction scheduling.
Reservat ...
with its index in the ROB for this purpose.
The contents of the buffer are used for data dependencies of other instructions scheduled in the buffer. The head of the buffer will be committed once its result is valid. Its dependencies will have already been calculated and committed since they must be ahead of the instruction in the buffer though not necessarily adjacent to it. Data dependencies between instructions would normally stall the pipeline while an instruction waits for its dependent values. The ROB allows the pipeline to continue to process other instructions while ensuring results are committed in order to prevent
data hazard
In the domain of central processing unit (CPU) design, hazards are problems with the instruction pipeline in CPU microarchitectures when the next instruction cannot execute in the following clock cycle, and can potentially lead to incorrect compu ...
s such as read ahead of write (RAW), write ahead of read (WAR) and write ahead of write (WAW).
There are additional fields in every entry of the buffer to support the extended algorithm:
* Instruction type (jump, store to memory, store to register)
* Destination (either memory address or register number)
* Result (value that goes to destination or indication of a (un)successful jump)
* Validity (does the result already exist?)
The consequences of the re-order buffer include precise
exceptions and easy
rollback
In political science, rollback is the strategy of forcing a change in the major policies of a state, usually by replacing its ruling regime. It contrasts with containment, which means preventing the expansion of that state; and with détente, w ...
control of
target address mis-predictions (branch or jump). When jump prediction is not correct or a nonrecoverable exception is encountered in the instruction stream, the ROB is cleared of all instructions (by setting the circular queue tail to the head) and reservation stations are re-initialized.
References
External links
Hardware Based Speculation - Prof. Dr. Ben H. JuurlinkReorder Buffer
Instruction processing
{{comp-sci-stub